1 Lineære ligningssystemer

Lineær algebra er en betegnelse for en samling af matematiske emner, der alle er relateret til løsninger af lineære ligningssystemer. Lineære ligningssystemer udgør dermed grundstenen i lineær algebra, og det er derfor afgørende at have en detaljeret viden om løsningerne hertil. Som udgangspunkt er vi hovedsagelig interesseret i lineære ligningssystemer over de reelle eller de komplekse tal, men da teorien viser sig at give mening og have anvendelser for andre typer af tal, også kaldet legemer (se Appendiks A), så vælger vi at behandle lineære ligningssystemer over et generelt legeme $\mathbb{F}$ . Hermed betegner $\mathbb{F}$ en mængde, hvorpå der er defineret addition og multiplikation, så de egenskaber, som vi er vant til fra de reelle tal, er opfyldt. Specielt giver det mening at dividere med elementer forskellig fra $0$ .

I det følgende vil vi anvende notationen indført i Appendiks A. Læseren der alene ønsker at fokusere på det reelle eller det komplekse tilfælde, kan i det følgende (og i Appendiks A) erstatte notationen $\mathbb{F}$ med hhv. $\mathbb{R}$ eller $\mathbb{C}$ .

1.1 Lineære ligninger

Med en lineær ligning i $n$ ordnede ubekendte $x_1, x_2, \ldots, x_n$ menes der en ligning $l$ af formen

$l: a_1 x_1 + a_2 x_2 + \ldots + a_n x_n = b, \tag{1.1}$ hvor $a_1,a_2,\ldots,a_n$ og $b$ er på forhånd valgte elementer i $\mathbb{F}$ . At de ubekendte er ordnede betyder blot, at vi på forhånd har fastlagt en rækkefølge af dem. I dette tilfælde er rækkefølgen understøttet af den valgte notation; dvs. $x_1$ er den første ubekendte, $x_2$ er den anden ubekendte etc. I det følgende vil ubekendte altid være antaget ordnet på denne vis, og vi vil derfor alene omtale $x_1,\ldots,x_n$ som værende ubekendte. Elementerne $a_1,a_2,\ldots,a_n$ kaldes for den lineære lignings koefficienter. Med en løsning til $l$ menes der en ordnet samling af skalarer $\alpha_1,\alpha_2,\ldots, \alpha_n \in \mathbb{F}$ , der opfylder relationen

$a_1 \alpha_1 + a_2 \alpha_2 + \ldots + a_n \alpha_n = b,$ i $\mathbb{F}$ . Sædvanligvis samler man skalarerne $\alpha_1,\ldots, \alpha_n$ i en vektor

${\bm{v}} = \begin{pmatrix} \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_n \\ \end{pmatrix} \in \mathbb{F}^n,$ og omtaler herefter denne vektor som en løsning til $l$ . Delmængden af $\mathbb{F}^n$ bestående af alle løsninger til $l$ kaldes for den lineære lignings løsningsmængde.

1.2 Lineære ligningssystemer

Med et lineært ligningssystem bestående af $m$ ligninger i $n$ ubekendte $x_1, \ldots, x_n$ , menes der en ordnet samling af lineære ligninger

i $n$ ubekendte. I det følgende vil vi også anvende notationen $L=(l_1, l_2, \ldots, l_m)$ om ovenstående lineære ligningssystem. Skalarerne $a_{ij} \in \mathbb{F}$ , for $1 \leq i \leq m, 1 \leq j \leq n$ , kaldes for ligningssystemets koefficienter. Hvis $b_i= 0$ for alle $i=1, \ldots, m$ , så kaldes ligningssystemet homogent.

Et element ${\bm{v}}$ i $\mathbb{F}^n$ kaldes en løsning til (1.2), hvis ${\bm{v}}$ er en løsning til hver af de lineære ligninger $l_1, \ldots,l_m$ . Delmængden $\mathcal{L}$ af $\mathbb{F}^n$ bestående af alle løsninger til (1.2) kaldes for løsningsmængden til (1.2).

Opgaven består nu i at besvare spørgsmål af følgende type:

Hvordan bestemmer og beskriver man løsningsmængden til (1.2)?
Hvor stor er løsningsmængden til (1.2); er den tom, er den endelig eller er den uendelig stor?
Hvis løsningsmængden er en endelig mængde, hvor mange løsninger er der så?

Hvis løsningsmængden er tom kaldes ligningssystemet for inkonsistent; i modsat fald kaldes systemet konsistent. Det er et ikke-trivielt udsagn, at et lineært ligningssystem aldrig kan have præcis $6$ løsninger. Tilsvarende er præcis $10$ , $12$ , $14$ , $15$ , $18$ og $20$ løsninger udelukket. Alle andre (positive) tal under $20$ kan optræde som antallet af løsninger til et lineært ligningssystem; dog aldrig når $\mathbb{F}$ er $\mathbb{R}$ eller $\mathbb{C}$ hvor der altid er præcis $1$ løsning, hvis antallet af løsninger er endeligt (og ikke nul). Følgende eksempel illustrerer, hvad vi kan forvente i det simpleste tilfælde.

Betragt et lineært ligningssystem

$a \cdot x =b, \tag{1.3}$ bestående af en enkelt ligning i en enkelt ubekendt $x$ . Løsningerne hertil er givet ved:

Hvis $a \neq 0$ , så er der præcis en løsning; nemlig $a^{-1} b$ .
Hvis $a = 0$ og $b=0$ , så er løsningsmængden lig $\mathbb{F}$ .
Hvis $a = 0$ og $b \neq 0$ , så er løsningsmængden tom.

1.3 Elementære operationer

Vi vil nu fokusere på konkrete metoder til bestemmelse af løsningsmængden $\mathcal{L}$ til et generelt lineært ligningssystem (1.2). I første omgang ønsker vi at sammenligne $\mathcal{L}$ med løsningsmængder for andre lineære ligningssystemer. Betragt, i den forbindelse, et lineært ligningssystem $L'$ givet ved

$\begin{aligned} \begin{alignedat}{8} l'_1 &: \quad &a'_{11} x_1 &+ \,&a'_{12} x_2 & +& \cdots &+& a'_{1n} x_n & = b'_1,\\ l'_2 &: \quad &a'_{21} x_1 &+ \,&a'_{22} x_2 &+ &\cdots &+& a'_{2n} x_n & = b'_2,\\ & &\vdots \quad& & \vdots \quad & & & & \vdots \quad & \quad\,\,\vdots\\ l'_m &: \quad &a'_{m1} x_1 &+ \,&a'_{m2} x_2 &+ &\cdots &+& a'_{mn} x_n & = b'_m, \end{alignedat} \end{aligned}\tag{1.4}$ og betegn løsningsmængden for dette system med $\mathcal{L}'$ . Vi er interesseret i at undersøge, hvornår $\mathcal{L}$ og $\mathcal{L}'$ er identiske, og vi definerer:

[Ækvivalente ligningssystemer] To lineære ligningssystemer, bestående af $m$ ligninger i $n$ ubekendte, kaldes ækvivalente, såfremt deres løsningsmængder er identiske.

Ækvivalente ligningssystemer fremkommer oftest ifm. anvendelse af de såkaldte elementære operationer. Elementære operationer anvendes på et lineært ligningssystem $(l_1,\ldots, l_m)$ , og resulterer i et nyt ækvivalent lineært ligningssystem $(l_1',\ldots,l_m')$ . Der er tre typer af elementære operationer, der hver især kun involverer en eller to af ligningssystemets lineære ligninger. I første omgang indfører vi følgende operationer på mængden af lineære ligninger:

Lad

$l: a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b,$ betegne en lineær ligning i $n$ ubekendte. For en skalar $\alpha \in \mathbb{F}$ defineres $\alpha \cdot l$ som den lineære ligning

$\alpha \cdot l: (\alpha a_1) x_1 + (\alpha a_2) x_2 + \cdots + (\alpha a_n) x_n = \alpha b.$ Givet endnu en lineær ligning

$l': a_1' x_1 + a_2' x_2 + \cdots + a_n' x_n = b',$ i de samme ubekendte, så defineres $l+l'$ som den lineære ligning

$l+l': (a_1+a_1')x_1 + (a_2+a_2') x_2+ \cdots + (a_n + a_n') x_n = b+b'.$

Den præcise definition af elementære operationer er da:

[Elementære operationer] En elementær operation på et lineært ligningssystem $L=(l_1,\ldots,l_m)$ er en af følgende tre typer af operationer ( $1 \leq i,j \leq m$ )

Ombyt to ligninger $l_i$ og $l_j$ , med $i \neq j$ , i $L$ .
Erstat ligning $l_i$ i $L$ med $\alpha \cdot l_i$ for en skalar $\alpha \in \mathbb{F} \setminus \{ 0 \}$ .
For $i \neq j$ og en skalar $\alpha \in \mathbb{F}$ erstattes ligning $l_i$ i $L$ med $l_i + \alpha \cdot l_j$ .

Quiz

Det oplyses, at det lineære ligningssystem $L'=(l_1',l_2')$ givet ved

$\begin{alignedat}{2} l_1' & : 3 x_1 + 2 x_2 + 4 x_3 & &= 4, \\ l_2' & : 3 x_1 + 3 x_2 + 1 x_3 & & = 2, \end{alignedat}$ fremkommer fra det lineære ligningssystem $L=(l_1,l_2)$ :

$\begin{alignedat}{2} l_1 & : 3 x_1 + 2 x_2 + 4 x_3 & &= 4, \\ l_2 & : 9 x_1 + 7 x_2 + 9 x_3 & & = 10, \end{alignedat}$ via en enkelt elementær operation. Angiv hvilke type af elementær operation, der kan være tale om.

Type I

Type II

Type III

Observer nu følgende vigtige pointe: hvis $L'=(l_1',\ldots,l_m')$ fremkommer fra $L=(l_1,\ldots,l_m)$ ved anvendelse af en elementær operation, så fremkommer $L$ også fra $L'$ ved anvendelse af en elementær operation på $L'$ . Antag f.eks., at vi har udført en elementær operation af type (Ⅰ.) for at opnå $L'$ fra $L$ . Så er $L'$ identisk med $L$ , på nær at der er byttet rundt på ligning $i$ og ligning $j$ . Vi kan altså opnå $L$ fra $L'$ ved at ombytte ligning $i$ og ligning $j$ i $L'$ ; det sidste svarer til at udføre en elementær operation af type (Ⅰ.) på $L'$ . Hvis derimod $L'$ fremkommer fra $L$ ved at gange den $i$ 'te ligning i $L$ med $\alpha \in \mathbb{F} \setminus \{ 0 \}$ , så skal man blot gange den $i$ 'te ligning i $L'$ med $\alpha^{-1}$ for at komme tilbage til $L$ . Endelig ses, at hvis $L'$ fremkommer ved, at man erstatter den $i$ 'te ligning i $L$ med $l_i + \alpha \cdot l_j$ , så skal man blot erstatte den $i$ 'te ligning i $L'$ med $l_i '- \alpha \cdot l_j'$ for at opnå $L$ . Med denne observation kan vi nu let bevise:

Hvis det lineære ligningssystem $L'=(l_1',\ldots,l_m')$ fremkommer fra $L=(l_1,\ldots,l_m)$ ved anvendelse af en successiv følge af elementære operationer, så er ligningssystemerne $L$ og $L'$ ækvivalente.

Bevis

Det er tilstrækkeligt at vise udsagnet i tilfældet, hvor $L'$ fremkommer fra $L$ ved anvendelse af en enkelt elementær operation. Start med at bemærke, at en løsning til $L$ også vil være en løsning til de lineære ligninger $\alpha \cdot l_i$ og $l_i + \alpha \cdot l_j$ . Specielt vil løsningsmængden $\mathcal{L}$ for $L$ være en delmængde af løsningsmængden $\mathcal{L}'$ for $L'$ . Et symmetrisk argument viser, at $\mathcal{L}'$ er en delmængde af $\mathcal{L}$ , og vi konkluderer derfor, at ligningssystemerne $L$ og $L'$ er ækvivalente.

Det modsatte af udsagnet i Lemma 1.6 er ikke nødvendigvis rigtig. Som eksempel herpå kan man betragte de lineære ligninger

$\begin{aligned} l_1: 0 x_1 + 1 x_2 &= 0, \\ l_2: 1 x_1 + 0 x_2 &= 0, \\ l_3: 0 x_1 + 0 x_2 &=1, \end{aligned}$ i to ubekendte $x_1$ og $x_2$ . De lineære ligningssystemer $L=(l_1,l_3)$ og $L'=(l_2,l_3)$ er da ækvivalente, idet løsningsmængden i begge tilfælde er tom. Derimod kan man ikke opnå $L'$ ud fra $L$ via en successiv følge af elementære operationer (hvorfor?).

1.4 Reducerede ligningssystemer

Vi skal nu beskrive en speciel type af lineære ligningssystemer, kaldet reducerede, hvor de tilsvarende løsningsmængder kan bestemmes via såkaldt baglæns substitution.

Reducerede systemer er karakteriseret ved placeringen af de såkaldte ledende koefficienter. Vi siger, at $a_i$ er den ledende koefficient for en lineær ligning

$l: a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b, \tag{1.5}$ hvis $a_i \neq 0$ og $a_j=0$ for $j<i$ . I givet fald siger vi, at $x_i$ er den ledende ubekendte for $l$ . Dette begreb kan selvfølgelig kun defineres, hvis ikke alle $a_i$ 'erne er lig $0$ .

Quiz

Angiv den ledende ubekendte for den lineære ligning

$\begin{alignedat}{2} l : 0 x_1 + 0 x_2 + 3 x_3 - 2 x_4 = 16. \end{alignedat}$

$x_1$

$x_2$

$x_3$

$x_4$

Såfremt $a_i$ er den ledende koefficient for (1.5), så skriver vi også

$l: a_i x_i + a_{i+1} x_{i+1} + \cdots + a_n x_n = b. \tag{1.6}$ At $x_1,\ldots,x_{i-1}$ ikke indgår i notationen (1.6) betyder dog ikke, at $l$ nu alene opfattes som en ligning i de ubekendte $x_i,\ldots,x_n$ . Ligning $l$ er stadig en lineær ligning i alle ubekendte $x_1, \ldots, x_n$ , og såfremt vi ønsker at understrege dette, så anvender vi notationen (1.5). F.eks. kunne vi vælge at skrive

$0 x_1 + 2 x_2 = 2,$ for at understrege, at den betragtede ligning er en ligning i to ubekendte $x_1$ og $x_2$ .

[Reducerede ligningssystemer] Et lineært ligningssystem

$\begin{aligned} \begin{alignedat}{8} l_1 &: \quad &a_{11} x_1 &+ \,&a_{12} x_2 & +& \cdots &+& a_{1n} x_n & = b_1,\\ l_2 &: \quad &a_{21} x_1 &+ \,&a_{22} x_2 &+ &\cdots &+& a_{2n} x_n & = b_2,\\ & &\vdots \quad& & \vdots \quad & & & & \vdots \quad & \quad\,\,\vdots\\ l_m &: \quad &a_{m1} x_1 &+ \,&a_{m2} x_2 &+ &\cdots &+& a_{mn} x_n & = b_m, \end{alignedat} \end{aligned}\tag{1.7}$ kaldes reduceret, hvis der findes en voksende følge af naturlige tal

$1 \leq d_1 < d_2 < \cdots < d_r \leq n,$ opfyldende

$x_{d_i}$ er den ledende ubekendte for $l_i$ for $1 \leq i \leq r$ .
For $r < i \leq m$ har $l_i$ ingen ledende koefficienter; dvs. $a_ {ij}=0$ for $j=1,\ldots,n$ .

Ovenstående definition inkluderer tilfældet $r=0$ , hvor alle koefficienter $a_{ij}$ er nul.

For et reduceret ligningssystem som ovenfor, der omtales de ubekendte $x_{d_1}, x_{d_2}, \ldots, x_{d_r}$ som ledende (til tider også bundne) ubekendte. De resterende ubekendte kaldes frie ubekendte.

Quiz

Angiv de frie ubekendte for det reducerede lineære ligningssystem

$\begin{alignedat}{4} l_1 & : 3 x_1 + 2 x_2 + & & 4 x_3 + && 5 x_4 + 6 x_5& &= 4, \\ l_2 & : & & 2 x_3- & & 4 x_4 -3 x_5 & & = 2, \\ l_3 & : & & & & 7 x_4 + 2 x_5 & &= 4. \end{alignedat}$

$x_1$

$x_2$

$x_3$

$x_4$

$x_5$

Reducerede lineære ligningssystemer kan løses via en metode kaldet baglæns substitution. For at beskrive denne metode, så vil vi anvende notationen indført i Definition 1.10. Idet der er $r$ ledende ubekendte, så må der være $n-r$ frie ubekendte. De frie ubekendte betegnes med $x_{e_1}, \ldots, x_{e_{n-r}}$ , for heltal $e_1,e_2,\ldots,e_{n-r}$ opfyldende, at

$1 \leq e_1 < e_2 < \cdots < e_{n-r} \leq n.$

Baglæns substitution foregår nu på følgende vis: Såfremt der eksisterer et $i>r$ med $b_i \neq 0$ , så vil ligning $l_i$ være givet ved

$l_i: 0 x_1 + 0 x_2 + \ldots + 0 x_n = b_i \neq 0, \tag{1.8}$ og den vil dermed ikke have løsninger. Løsningsmængden til (1.7) er dermed tom, med mindre $b_i=0$ for alle $i>r$ . Hvis derimod $b_i=0$ for alle $i>r$ , så kan vi se bort fra ligningerne $l_i$ , for alle $i>r$ , idet de alle er trivielle; dvs. på formen

$0 x_1+0 x_2 + \cdots + 0 x_n = 0,$ og dermed er opfyldt for alle konkrete værdier af de ubekendte. Vi har dermed reduceret til tilfældet, hvor $r=m$ . Omskriv nu ligning $l_i$ til formen

$\tilde l_i : x_{d_i} = a_{i d_i}^{-1} \biggl( b_i- \sum_{j > d_i} a_{ij} x_j \biggr),$ og bemærk, at dette angiver værdien af $x_{d_i}$ , såfremt værdierne for de efterfølgende ubekendte $x_{d_i+1},\ldots, x_n$ allerede er fastlagt. Dette leder nu frem til følgende procedure til bestemmelse af samtlige løsninger til det lineære ligningssystem: start med at vælge vilkårlige værdier for de frie ubekendte $x_{e_1}, \ldots, x_{e_{n-r}}$ . Herefter bestemmer ligning $\tilde l_r$ værdien af $x_{d_r}$ , og med denne værdi for $x_{d_r}$ så bestemmer ligning $\tilde l_{r-1}$ nu værdien af $x_{d_{r-1}}$ . Derefter fastlægger $\tilde l_{r-2}$ værdien af $x_{d_{r-2}}$ , etc.

Vi konkluderer:

Løsningsmængden til det reducerede lineære ligningssystem (1.7) kan beskrives ved:

Hvis $b_i=0$ for $i>r$ , så vil ethvert valg af skalarer $\alpha_{e_1}, \ldots, \alpha_{e_{n-r}} \in \mathbb{F}$ kunne entydigt udvides til en løsning $\alpha_1,\ldots, \alpha_n$ til (1.7).
Hvis der eksisterer et $i>r$ med $b_i \neq 0$ , så er løsningsmængden til (1.7) den tomme mængde.

Såfremt der ikke er frie ubekendte (dvs. hvis $r=n$ ), så skal første udsagn ovenfor forstås, som at ligningssystemet har en entydig løsning.

Ovenstående sætning illustreres bedst via et eksempel:

Vi ønsker at bestemme løsningsmængden for det reducerede lineære ligningssystem ( $\mathbb{F}= \mathbb{R}$ )

$\begin{alignedat}{3} l_1 & : 1 x_1 + 2 x_2 + & & 3 x_3 + 4 x_4& & = 4, \\ l_2& : & & 2 x_3 + 4 x_4 & & = 2, \end{alignedat} \tag{1.9}$ og starter med at bemærke, at $d_1=1 < d_2=3$ bestemmer placeringen af de ledende koefficienter. Specielt er $r=2$ , og vi vil, ifølge Proposition 1.12, have en (entydig) løsning for ethvert valg af værdier $\alpha_2$ og $\alpha_4$ for hhv. $x_2$ og $x_4$ . Vi anvender baglæns substitution for at opnå de tilsvarende værdier for $\alpha_1$ og $\alpha_3$ . Først bestemmer $l_2$ værdien af $\alpha_3$

$\alpha_3 = 2^{-1} (2-4\alpha_4) = 1- 2 \alpha_4,$ og herefter opnås værdien for $\alpha_1$ via ligning $l_1$ :

$\begin{aligned} \alpha_1 & = 4 - 4 \alpha_4 - 3 \alpha_3 - 2 \alpha_2 \\ & = 4- 4 \alpha_4 - 3 (1-2 \alpha_4)-2 \alpha_2 \\ & = 1 - 2 \alpha_2 + 2 \alpha_4. \end{aligned}$ Løsningsmængden til (1.9) består altså af mængden af vektorer på formen

$\begin{pmatrix} 1 - 2 \alpha_2 + 2 \alpha_4 \\ \alpha _2 \\ 1-2\alpha_4 \\ \alpha_4 \end{pmatrix} \in \mathbb{F}^4, \tag{1.10}$ hvor $\alpha_2$ og $\alpha_4$ kan vælges frit blandt elementerne i $\mathbb{F}$ . Bemærk, at vi også kan omskrive (1.10) til

$\begin{pmatrix} 1 \\ 0 \\ 1\\ 0 \end{pmatrix} + \alpha_2 \begin{pmatrix} - 2 \\ 1 \\ 0 \\ 0 \end{pmatrix} + \alpha_4 \begin{pmatrix} 2 \\ 0 \\ -2 \\ 1 \end{pmatrix} , \tag{1.11}$ hvor de indgående vektorer er karakteriseret ved:

$\begin{aligned} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} &= \text{den entydige løsning til \href{#ekslig}{(1.9)} med værdier af } x_2 \text{ og }x_4\text{ lig } 0. \\ & \\ \begin{pmatrix} -2 \\ 1 \\ 0 \\ 0 \end{pmatrix} &= \begin{array}{l} \text{den entydige løsning til den homogene version af \href{#ekslig}{(1.9)} } \\ \text{med værdier af } x_2 \text{ og } x_4\text{ lig hhv. } 1 \text{ og } 0 \end{array} \\ & \\ \begin{pmatrix} 2 \\ 0 \\ -2 \\ 1 \end{pmatrix} &= \begin{array}{l} \text{den entydige løsning til den homogene version af \href{#ekslig}{(1.9)} } \\ \text{med værdier af } x_2\text{ og }x_4\text{ lig hhv. }0\text{ og }1 \end{array} \end{aligned}$

Vi introducerer nu begrebet fuldstændigt reduceret lineært ligningssystem, der betegner et reduceret lineært ligningssystem af en speciel pæn form.

[Fuldstændigt reducerede lineære ligningssystemer] Et reduceret lineært ligningssystem (1.7) kaldes fuldstændigt reduceret, hvis der for $i=1,\ldots,r$ og $j=1,\ldots,m$ gælder, at koefficienten $a_{j d_i}$ , til $x_{d_i}$ i $l_j$ , er lig $0$ hvis $j \neq i$ og lig $1$ hvis $i=j$ .

Quiz

Angiv værdierne for skalarerne $\alpha$ og $\beta$ så det lineære ligningssystem

$\begin{alignedat}{4} l_1 & : 1 x_1 + 2 x_2 + & & 0 x_3 + && 0 x_4 + 6 x_5& &= 3, \\ l_2 & : & & 1 x_3- & & \beta x_4 -3 x_5 & & = 2, \\ l_3 & : & & & & \alpha x_4 + 2 x_5 & &= 4, \end{alignedat}$ er fuldstændigt reduceret.

$\alpha = 0, \beta = 0$

$\alpha =1, \beta = 0$

$\alpha =0, \beta = 1$

$\alpha =1, \beta = 1$

Det bemærkes, at de bundne ubekendte i et fuldstændigt reduceret lineært ligningssystem kun optræder med koefficient forskellig fra $0$ i en enkelt af systemets ligninger. Dermed kan værdierne af de bundne ubekendte umiddelbart aflæses ud fra værdierne af de frie ubekendte. Mere præcist er den $i$ 'te ligning i systemet ækvivalent med

$x_{d_i} = b_i - (\text{udtryk der alene afhænger af }x_{e_1}, \ldots, x_{e_{n-r}}\text{).}$ Baglæns substitution er dermed simplere at udføre end for almindelige reducerede ligningssystemer.

Ligningssystemet

$\begin{alignedat}{3} l_1 & : 1 x_1 + 2 x_2 + & & 3 x_3 + 4 x_4 & & = 4, \\ l_2 & : & & 2 x_3 + 4 x_4 & & = 2, \end{alignedat} \tag{1.12}$ fra Eksempel 1.13 er ikke fuldstændigt reduceret. Multiplicerer man $l_2$ med $\frac{1}{2}$ , så opnår man

$\begin{alignedat}{3} l_1 & : 1 x_1 + 2 x_2 + & & 3 x_3 + 4 x_4 & &= 4, \\ l'_2 & : & & 1 x_3 + 2x_4 & & = 1, \end{alignedat} \tag{1.13}$ som heller ikke er fuldstændigt reduceret. Til gengæld kan man nu trække $3 \cdot l_2'$ fra $l_1$ og opnå et ligningssystem

$\begin{alignedat}{3} l'_1 & : 1 x_1 + 2 x_2 + & & 0 x_3 - 2 x_4 &&= 1, \\ l'_2 & : & & 1 x_3 + 2x_4 && = 1, \end{alignedat} \tag{1.14}$ der er fuldstændigt reduceret og ækvivalent med (1.12). I ovenstående proces er alle de indgående ligningssystemer reducerede. Bemærk også, at $l_1'$ og $l_2'$ umiddelbart bestemmer en løsning $\alpha_1,\alpha_2,\alpha_3,\alpha_4$ ud fra værdierne af $\alpha_2$ og $\alpha_4$ . Mere præcist giver $l_1'$ at

$\alpha_1 = 1 - 2 \alpha_2 + 2 \alpha_4,$ mens $l_2'$ bestemmer

$\alpha_3 = 1- 2\alpha_4,$ hvilket er identisk med, hvad vi fandt i Eksempel 1.13.

1.5 Gauss elimination

I starten af 1800-tallet beskrev C.F. Gauss banen for en asteroide ved navn Pallas. Beskrivelsen byggede på flere års observationer og dertilhørende databehandling. En del af databehandlingen bestod i at løse et lineært ligningssystem bestående af seks ligninger i seks ubekendte, og i den forbindelse anvendte Gauss en algoritme til løsning af lineære ligningssystemer, som vi nu skal beskrive. Gauss elimination er en algoritme til at omforme et generelt lineært ligningssystem

$\begin{aligned} \begin{alignedat}{8} l_1 &: \quad &a_{11} x_1 &+ \,&a_{12} x_2 & +& \cdots &+& a_{1n} x_n & = b_1,\\ l_2 &: \quad &a_{21} x_1 &+ \,&a_{22} x_2 &+ &\cdots &+& a_{2n} x_n & = b_2,\\ & &\vdots \quad& & \vdots \quad & & & & \vdots \quad & \quad\,\,\vdots\\ l_m &: \quad &a_{m1} x_1 &+ \,&a_{m2} x_2 &+ &\cdots &+& a_{mn} x_n & = b_m, \end{alignedat} \end{aligned}\tag{1.15}$ til et reduceret lineært ligningssystem ved hjælp af elementære operationer. Sammen med Lemma 1.6 og Proposition 1.12 opnår man herved en metode til at løse generelle lineære ligningssystemer.

Den grundlæggende observation ifm. Gauss elimination er, at man via en følge af elementære operationer på (1.15) kan opnå et nyt ligningssystem på formen

$\begin{aligned} l_1' : a_{11}' x_1 +\, a_{12}' x_2 + \cdots + a_{1n}' x_n \,\, & = b_1',\\ l_2' : \qquad\quad\,\,\,\,\, a_{22}' x_2 + \cdots + a_{2n}' x_n \,\,& = b_2',\\ \quad\qquad\vdots\quad\qquad\quad\qquad \vdots \,\,\,\quad & \,\,\,\quad\vdots \\ l_m' : \qquad\quad\,\,\,\, a_{m2}' x_2 + \cdots + a_{mn}' x_n & = b_m' \end{aligned}\tag{1.16}$ dvs. et ligningssystem hvor alle koefficienter til $x_1$ er nul for ligningerne $l_2',\ldots, l_m'$ . Dette kan f.eks. gøres på følgende vis:

Hvis $a_{11}=a_{21}= \cdots = a_{m1}=0$ , så er (1.15) allerede på formen (1.16).
Hvis der eksisterer et med , så udføres følgende successive følge af elementære operationer på (1.15):
1. Erstat ligning $l_j$ med $l_j -a_{j1}a_{i1}^{-1} l_i$ , for $j \neq i$ .
2. Ombyt ligning $l_i$ med ligning $l_1$ (hvis $i=1$ så udelades dette).

Vi er nu parate til at beskrive algoritmen bag Gauss elimination. Algoritmen er rekursiv i antallet af ubekendte $n$ , så vi antager, at vi allerede har beskrevet, hvordan systemer med $n-1$ ubekendte kan bringes på reduceret form. Vi skal da beskrive, hvordan et ligningssystem (1.15) med $n$ ubekendte kan bringes på reduceret form. Vi starter med at bringe (1.15) på formen (1.16) som beskrevet ovenfor. Hvis $n=1$ , så har vi hermed opnået et reduceret system. Hvis derimod $n>1$ , så opdeler vi i tilfældene $a_{11}' = 0$ og $a_{11}' \neq 0$ . I tilfældet hvor $a_{11}'=0$ , der kan vi opfatte (1.16) som et system i de $n-1$ ubekendte $x_2,x_3, \ldots, x_n$ , og dette system kan bringes på reduceret form via vores rekursive antagelse. Hvis derimod $a_{11}' \neq 0$ , så er $x_1$ en ledende ubekendt for $l_1'$ . Ligningssystemet $(l_2',\ldots,l_m')$ kan vi samtidig opfatte som et system i de $n-1$ ubekendte $x_2,\ldots,x_n$ , og hvis vi bringer denne del på reduceret form $(l_2'',\ldots,l_m'')$ , så vil $(l_1', l_2'',\ldots,l_m'')$ også være et reduceret ligningssystem.

Lad os beskrive løsningsmængden til det lineære ligningssystem ( $\mathbb{F} =\mathbb{R}$ )

$\begin{aligned} 2 x_1 + 2 x_2 + 2 x_3 + 2 x_4& = 2, \\ 2 x_1 + 2 x_2 + 2 x_3 + 3 x_4& = 4, \\ 4 x_1 + 4 x_2 + 5 x_3 + 6 x_4 &= 6. \end{aligned}\tag{1.17}$ Vi starter med at anvende Gauss elimination for at opnå et ækvivalent reduceret lineært ligningssystem. Først trækker vi den øverste ligning fra den midterste, samt $2$ gange fra den nederste. Herved opnås

$\begin{aligned} 2 x_1 + 2 x_2 + 2 x_3 + 2x_4 & = 2 \\ 0 x_1 + 0 x_2 + 0 x_3 + 1x_4 & = 2 \\ 0 x_1 + 0 x_2 + 1 x_3 + 2 x_4& = 2 . \end{aligned}\tag{1.18}$ Den beskrevne algoritme beder os herefter om at koncentrere os om de nederste to ligninger, og om at opfatte disse som ligninger i de ubekendte $x_2, x_3$ og $x_4$ . Herefter skal vi udføre elementære operationer, så vi opnår en form lignende (1.16). Da det sidste allerede er tilfældet, går vi videre til næste skridt i algoritmen. Her bliver vi bedt om at opfatte de to nederste ligninger som ligninger i de ubekendte $x_3$ og $x_4$ . Vi sørger herefter for, at disse ligninger har formen præciseret ved (1.16). Dette opnås ved at ombytte de to nederste ligninger. I alt har vi nu opnået ligningssystemet

$\begin{aligned} 2 x_1 + 2 x_2 + 2 x_3 + 2x_4 & = 2 \\ 0 x_1 + 0 x_2 + 1 x_3 + 2 x_4& = 2 \\ 0 x_1 + 0 x_2 + 0 x_3 + 1x_4 & = 2, \end{aligned}\tag{1.19}$ som er reduceret, og som derfor kan løses via baglæns substitution. Vi kan anvende samme fremgangsmåde som i Eksempel 1.13, og finder, at løsningsmængden består af elementer på formen

$\begin{pmatrix} 1 \\ 0 \\ -2\\ 2 \end{pmatrix} + \alpha_2 \begin{pmatrix} -1 \\ 1 \\ 0 \\ 0 \end{pmatrix} , \tag{1.20}$ hvor $\alpha_2$ kan vælges frit blandt elementerne i $\mathbb{F}$ .

Den opmærksomme læser har formentlig allerede observeret, at vi ifm. Gauss elimination alene har anvendt elementære operationer af type (Ⅰ.) og type (Ⅲ.). Såfremt man også anvender type (Ⅱ.) operationer, så kan det betragtede ligningssystem bringes på fuldstændigt reduceret form via en algoritme kaldet Gauss-Jordan elimination. Idet vi allerede har introduceret Gauss elimination, så vil vi her alene beskrive, hvordan et reduceret lineært ligningssystem kan bringes på fuldstændigt reduceret form.

Så betragt et reduceret lineært ligningssystem

$\begin{aligned} \begin{alignedat}{8} l_1 &: \quad &a_{11} x_1 &+ \,&a_{12} x_2 & +& \cdots &+& a_{1n} x_n & = b_1,\\ l_2 &: \quad &a_{21} x_1 &+ \,&a_{22} x_2 &+ &\cdots &+& a_{2n} x_n & = b_2,\\ & &\vdots \quad& & \vdots \quad & & & & \vdots \quad & \quad\,\,\vdots\\ l_m &: \quad &a_{m1} x_1 &+ \,&a_{m2} x_2 &+ &\cdots &+& a_{mn} x_n & = b_m, \end{alignedat} \end{aligned}\tag{1.21}$ Vi anvender notation som i Definition 1.10, og kan da betragte følgende successive operationer på (1.21). Vi starter med at udføre de elementære operationer

For $1 \leq i \leq r$ ganges ligning $l_i$ med $a_{id_i}^{-1}$ .

der bringer (1.21) på en form

$\begin{alignedat}{8} l_1 &: \quad &a'_{11} x_1 &+ \,&a'_{12} x_2 & +& \cdots &+& a'_{1n} x_n & = b'_1,\\ l_2 &: \quad &a'_{21} x_1 &+ \,&a'_{22} x_2 &+ &\cdots &+& a'_{2n} x_n & = b'_2,\\ & &\vdots \quad& & \vdots \quad & & & & \vdots \quad & \quad\,\,\vdots\\ l_m &: \quad &a'_{m1} x_1 &+ \,&a'_{m2} x_2 &+ &\cdots &+& a'_{mn} x_n & = b'_m, \end{alignedat} , \tag{1.22}$ hvor alle de ledende koefficenter er lig $1$ . Herefter kan man udføre

For et givet $2 \leq i \leq r$ erstattes ligning $l_j$ med $l_j - a'_{jd_i} \cdot l_i$ for $1 \leq j <i$ .

på det lineære ligningssystem (1.22) og opnå et fuldstændigt reduceret ligningssystem. Det overlades til læseren at indse dette (se evt. Eksempel 1.16 for et eksempel på denne metode).

1.6 Et vigtigt resultat

Det følgende resultat beskriver løsningsmængden til et homogent lineært ligningssystem med flere ubekendte end ligninger. Resultatet er yderst vigtigt, og danner bl.a. grundlaget for basisbegrebet, som vi skal studere i Kapitel 7.

Et homogent lineært ligningssystem

$\begin{aligned} \begin{alignedat}{8} l_1 &: \quad &a_{11} x_1 &+ \,&a_{12} x_2 & +& \cdots &+& a_{1n} x_n & = 0,\\ l_2 &: \quad &a_{21} x_1 &+ \,&a_{22} x_2 &+ &\cdots &+& a_{2n} x_n & = 0,\\ & &\vdots \quad& & \vdots \quad & & & & \vdots \quad & \quad\,\,\vdots\\ l_m &: \quad &a_{m1} x_1 &+ \,&a_{m2} x_2 &+ &\cdots &+& a_{mn} x_n & = 0, \end{alignedat} \end{aligned}\tag{1.23}$ med $m <n$ har en løsning forskellig fra $\bm{0}$ .

Hvilke af nedenstående homogene ligningssystemer har en løsning forskellig fra $\bm{0}$

$x + y = 0$

$\begin{aligned} x + y &= 0\\ x - y &= 0 \end{aligned}$

$\begin{aligned} x + y - z &= 0\\ x - y + z &= 0 \end{aligned}$

Bevis

Ved anvendelse af Gauss elimination kan vi antage, at (1.23) er et homogent reduceret lineært ligningssystem. Idet antallet af ledende ubekendte er mindre end eller lig antallet af ligninger $m$ , så vil der eksistere mindst $n-m>0$ frie ubekendte. Samtidig fortæller Proposition 1.12, at der vil eksistere løsninger til ligningssystemet, der antager arbitrære værdier for de frie ubekendte. Dermed eksisterer der nødvendigvis en løsning forskellig fra $\bm{0}$ .